1. Field of the Invention
The present invention relates generally to the field of operations research and more particularly to the field of production management.
2. Description of the Related Art
The field of Operations Research (OR) is concerned with the mathematical or scientific analyses of processes and provides tools that may be used in making decisions. For example, OR provides guidance on the optimal allocation and deployment of limited resources (such as people, machines, time, materials, storage, transportation and the like) through the use of modeling and mathematical algorithms. The field of production planning and scheduling may be thought of as a subset of the field of OR and is concerned with the optimal deployment of limited resources to efficiently produce an item or items in response to an order (a request for a specified number of a specified item by a specified date). Resources may have a certain availability defined by an availability profile and a certain capacity, which may be represented by any number that represents the power (of one or more machines over time, for example) to build something. A process specifies the manner in which resources are used to produce an item. The production of the items comprising the order may be subject to a number of constraints, such as limits on manpower, machine availability, inability to produce on Sundays or most any other limit on production. Those involved with such productions use both plans and schedules to manage the long and short term production, respectively. A plan may be thought of as a long-term view of the production over predefined time quanta (herein called a time bucket T), whereas a schedule may be thought of as a shorter term set of activities necessary to achieve the desired production, albeit at a relatively lower level of granularity.
In attempting to solve complex real world problems, it is seldom possible to jump from the problem directly to a real world solution. Instead, a modeling process is used, whereby the real world problem is transformed into a mathematical problem, which is then modeled as a set of equations. The model is a set of variables and a set of constraints that define the relationship between each of the defined variables. The mathematical model may then be susceptible to being solved by one or more algorithms, leading to a mathematical solution. Such a mathematical solution may then be interpreted in light of the real world problem to arrive at the real world solution. The set of feasible solutions to such problems may be graphically represented as an n-dimensional space, where n is the number of variables in the mathematical model of the problem. Problems addressed by OR may be divided into polynomial problems and non-polynomial (hereafter, NP) problems. Problems that are classified as polynomial problems include those for which an algorithm exists (or may be devised) of polynomial complexity that solves the problem. In contrast, NP problems encompass those that are not subject to being solved by an algorithm of polynomial complexity. An important concept within the OR field is that of convexity. Convex solution domains are those in which all points on the segment joining any two points within the solution domain also belong to the solution domain. Non-convex solution domains are those in which the above statement does not hold true.
The problem of producing a schedule of activities is a non-convex problem, as well as being a NP problem. One example of such non-convexity is the problem of scheduling activities and allocating resources to such activities. For example, two or more activities may require the same resource, such as a machine tool, for example. Both activities cannot use the machine tool at the same time, which forces a decision as to which activity is to use the resource. Each decision itself may entail a number of other decisions, each of which may need to be evaluated. These decisions may be represented as a branching tree of decisions. The sheer number of such decision points often leads to a computationally unmanageable number of branching decisions, a condition also known as a combinatorial explosion. Combinatorial optimization is the sub branch of OR that addresses NP problems. Planning methodologies may be used to solve the linear relaxation of the problem and uses a time bucketing approximation and scheduling methodologies are used to solve the remaining portions of the problem.
Linear programming (hereafter, LP) methods are used to solve planning problems. LP methodologies address problems with linear equations, of the form Σaij xj˜bi, where the symbols ≧, ≦ or = may be substituted for the˜symbol. Such LP problems are often solved by means of the simplex algorithm (or variations thereof), which is a matrix procedure for solving linear programs (usually to maximize or minimize a quantity known as the objective). To do so, the linear equation is placed in standard form, a so-called simplex tableau is created and the known simplex method is recursively applied to the simplex tableau until the desired maximum or minimum solution is obtained. Therefore, the generation of a plan involves finding the linear subparts of the production problem and to solve each of the linear subparts using the simplex algorithm. Non-convex problems, however, cannot be solved using the simplex algorithm.
Conventionally, therefore, LP methods are applied to the linear subparts of the scheduling problem to generate the plan. The planning model may also be characterized as a relaxation of the production problem with time buckets, which entails no precise lead times and no exact continuous balance of materials. The scheduling model, on the other hand, specifies the start and end times of each activity, identifies what resources are needed and when such resources are needed, from the raw materials to the finished product, for example.
Communication between the planning model and the scheduling model is customarily carried out through the maintenance of resource and item profiles. Such conventional communication between the planning and scheduling models, however, is awkward, as both models typically must share “constraint” objects or must each update both resource and item profiles, which are based on very different mathematical models and data structures. Such communication through “constraint” objects or through updating resource and item profiles has proven to be one of the main limitations to an efficient communication between the two models.
What are needed, therefore are methods and systems enabling a more efficient communication between the planning and scheduling models. What are also needed are methods and systems enabling the use of the plan generated through the planning model (the LP relaxation of the production problem) as a hint when generating a schedule. What are also needed are methods and systems enabling the launching of a new and updated plan in the middle of a scheduling algorithm (i.e., with only a partial schedule completed) to update the results thereof.